package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ListNode;

/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 * <p>
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 */
public class code61_旋转列表 {
    public static void main(String[] args) {
        ListNode node = ListNode.createListNode(new int[]{
                1,2
        });
        node = new code61_旋转列表().rotateRight(node,1);
        ListNode.showListNode(node);
    }

    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null){
            return head;
        }
        int speed = 1;
        ListNode change = null;
        ListNode nowNode = head;
        ListNode end;
        while (nowNode.next != null) {
            speed++;
            nowNode = nowNode.next;
        }
        end = nowNode;
        k = k % speed;
        nowNode = head;
        speed = 0;
        while (k > 0 && nowNode != null) {
            if (speed >= k) {
                if (change == null) {
                    change = head;
                } else {
                    change = change.next;
                }
            }
            speed++;
            nowNode = nowNode.next;
        }
        if (change != null) {
            end.next = head;
            head = change.next;
            change.next = null;
        }
        return head;
    }
}
